package org.example.l0;

import org.example.l2.TreeNode;
import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

public class buildTree {


    @Test
    void aa() {
        buildTree(new int[]{4, 3, 1, 2}, new int[]{1, 2, 3, 4});
    }

    public TreeNode buildTree(int[] preorder,
                              int[] inorder) {
        Map<Integer, Integer> inOrderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inOrderMap.put(inorder[i], i);
        }

        TreeNode treeNode = buildTree(preorder, inOrderMap, 0, inorder.length - 1, 0);
        return treeNode;
    }

    public TreeNode buildTree(int[] preorder,
                              Map<Integer, Integer> inOrderMap,
                              int start,
                              int end,
                              int offset) {
        if (start > end) {
            return null;
        }

        int v = preorder[start];
        Integer idx = inOrderMap.get(v);
        int leftNodes = idx - offset;

        TreeNode node = new TreeNode(v);
        node.left = leftNodes == 0 ? null : buildTree(preorder, inOrderMap, start + 1, start + leftNodes, offset);
        node.right = buildTree(preorder, inOrderMap, start + leftNodes + 1, end, idx + 1);

        return node;
    }
}
